// 0. 括号-22-括号生成
// 1. 组合-77-组合 
// 2. 组合-216-组合之和3 
// 3. 组合-17-电话号码
// 4. 组合-39-组合之和1 
// 5. 组合-40-组合之和2  i > dep && arr[i] - arr[i - 1]
// 6. 分割-131-分割回文串
// 7. 分割-93-复原ip地址 
// 8. 分割-78-求子集
// 9. 分割-90-求子集2 i > dep && arr[i] - arr[i - 1]
// 10. 排列-46-全排列 
// 11. 排列-47-全排列2  i > dep && arr[i] - arr[i - 1] && !used[i]
// 12. 二维-51-n皇后
// 13. 单词搜索











// 0.组合生成 3 
// 题解：根据n生成有效的括号
// 思路: 当left< n 先加左；当right< left 加右 结束条件cur.length ===2n
// 注意：非回溯解法
function generateBucket(n) {
  let res = [];
  const dfs = (cur, left, right) => {
    if (cur.length === 2 * n) {
      return res.push(cur);
    }
    if (left < n) {
      dfs(cur + "(", left + 1, right)
    }
    if (right < left) {
      dfs(cur + ')', left, right + 1)
    }
  }
  dfs('', 0, 0)
  return res;
}
console.log(generateBucket(3))
// 括号问题----
// 1. 括号生成
// 2. 括号是否有效（stack）
// 3. 最长的有效括号（stack）


// 1. 组合 
// 题解：输出1-n的k个数组合，所有可能，不能重复
// 思路：【终止条件】: temp数组数量达到k; 【循环逻辑】: 正序，start为dep, 起始1，,<=n,i递增;【优化剪枝】: 1.循环结束点 n-（k-temp.length）+ 1
// 注意：1-n, 所以循环dep从1开始; n-（k-temp.length）+ 1 比如n=4， k=4 第一层取了1，不能取2 因为2后面只能取34 不够k了，索引最远能到位置 k-temp.length 还需要几个，n - (k-temp.length) 循环到此处后面还能有几个 ，target是k
function combin(n, k) {
  let res = [];
  let temp = [];
  let dep = 1
  const backtracking = (temp, target, dep) => {
    if (temp.length === k) {
      return res.push([...temp]);
    }
    for (let i = dep; i <= n; i++) {  // 这里需要
      temp.push(i);
      backtracking(temp.slice(), target, i + 1);
      temp.pop()
    }
  }
  backtracking(temp, k, dep)
  return res
}
console.log(combin(4, 2)) // n = 4, k = 2


// 2.组合之和3 
// 题解：找出所有相加之和为 n 的 k 个数的组合 使用1-9， 每个数只能使用一次
// 思路：【解空间】: 1 - 9; 【终止条件】: temp数组数量达到k， sum 总和为n; 【循环逻辑】: 正序，start为dep，dep递增;【优化剪枝】: 1.循环结束点 9 -（k-temp.length）+ 1; 2. sum > n,return
// 注意：dep为i+1 sum也要和temp一样回溯， target是和n
var combinationSum3 = function (k, n) {
  const temp = [];
  const res = [];
  const dep = 1
  const backtracking = (temp, target, dep) => {

    if (target === 0 && temp.length === k) {
      return res.push(temp)
    }

    for (let i = dep; i <= 9 + 1; i++) {
      if (target < i) break;
      temp.push(i);
      backtracking(temp.slice(), target - i, i + 1)
      temp.pop()
    }
  }
  backtracking(temp, n, dep)
  return res
};

console.log("combinationSum3: ", combinationSum3(9, 45)) //  n = 7， k = 3

// 3.电话号码
// digits = "23"
// 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 题解：输出键盘数字，可能组成的单词
// 思路：【解空间】: dep对应的map的分解value 如1 对应的a，b，c; 【终止条件】: temp数组数量达到k; 【循环逻辑】: 正序，start为dep, 初始0， dep递增;【优化剪枝】: 无
// 注意：dep为dep+1 循环的是对象 const v of map[n[dep]]， targeet是长度k
function telNum(digits) {
  let k = digits.length;
  let map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
  if (!k) return [];
  if (k === 1) return map[digits].split('')

  let res = [];
  let temp = [];
  let dep = 0;

  function backtracking(temp, target, dep) {
    if (temp.length === target) {
      return res.push(temp.join(''))
    }
    for (const v of map[digits[dep]]) {
      temp.push(v);
      backtracking(temp.slice(), target, dep + 1)
      temp.pop()
    }
  }
  backtracking(temp, k, dep)
  return res;
}
console.log(telNum('23'))

// 4. 组合之和1 
// 题解：在arr中找出和为target的组合，数字可重复使用
// 思路：【解空间】: arr 【终止条件】: target=0; 【循环逻辑】: 正序，start为dep, 初始0，dep为i，target为当前差值;【优化剪枝】: 1. 当剩余target 小于arr[i]的时候退出，随便剪一个就是负数了
// 注意: dep为i，target是差值 i没有加1 因为可以重复
function combinationSum(arr, target) {
  arr.sort((a, b) => a - b) // 1
  let res = [];
  let temp = [];
  let dep = 0;
  function backtracking(temp, target, dep) {
    if (target === 0) {
      res.push(temp)
      return
    }
    for (let i = dep; i < arr.length; i++) {
      if (target < arr[i]) break
      temp.push(arr[i])
      backtracking(temp.slice(), target - arr[i], i);
      temp.pop()
    }
  }
  backtracking(temp, target, dep)
  return res
}
console.log(combinationSum([2, 3, 6, 7], 7)) // candidates = [2,3,6,7], target = 7  [[2,2,3],[7]]


// 5. 组合2 candidates = [2,3,6,7], target = 7  [[7]]
// 题解：在arr中找出和为target的组合，数字不可重复使用
// 思路：【解空间】: arr 【终止条件】: target=0; 【循环逻辑】: 正序，start为dep, 初始0，dep为i，target为当前差值;【优化剪枝】: 1.当剩余target 小于arr[i]的时候退出，随便剪一个就是负数了；2.当i < dep && arr[i] - arr[i - 1] 判断相邻两个相等，则continue
// 注意： dep为i+1，target是差值， continue很重要，最前面最好sort一下
function combinationSum2(arr, target) {
  arr.sort((a, b) => a - b) // 1
  let res = [];
  let temp = [];
  let dep = 0;

  const backtracking = (temp, target, dep) => {
    if (0 === target) {
      res.push(temp)
      return;
    }
    for (let i = dep; i < arr.length; i++) {
      if (target < arr[i]) break
      if (i > dep && arr[i] - arr[i - 1]) continue  // 2
      temp.push(arr[i])
      backtracking(temp.slice(), target - arr[i], i + 1)
      temp.pop()
    }
  }
  backtracking(temp, target, dep)
  return res;
}
console.log(combinationSum2([2, 3, 6, 7], 7))

// 6.分割回文串
// 题解：给一个字符串将其分割成子串，使每个子串都是回文
// 思路：【解空间】: str 【终止条件】: dep >= len; 【循环逻辑】: 正序，start为dep, 初始0，dep为i+1【优化剪枝】: 1.不是回文则continue
// 注意：放入的元素是s.slice(dep, i+1)
const isPalindrome = (s, l, r) => {
  for (let i = l, j = r; i < j; i++, j--) {
    if (s[i] !== s[j]) return false;
  }
  return true;
}
function partition(s) {
  let res = [];
  let temp = [];
  let len = s.length;

  const dfs = (temp, target, dep) => {
    if (dep >= target) {
      return res.push(Array.from(temp))
    }
    for (let i = dep; i < len; i++) {
      if (!isPalindrome(s, dep, i)) continue;
      temp.push( s.slice(dep, i + 1))
      dfs(temp.slice(), target,i + 1) // 这里注意是i+1
      temp.pop()
    }
  }

  dfs(temp, len, 0);
  return res;
}
console.log(partition('abb')) // s = "aab" [["a","a","b"],["aa","b"]]


// 7. 复原ip地址 
// 题解：将一串数字切割成符合ip规则的四个整数，返回所有可能
// 思路：【解空间】: str 【终止条件】: temp.length ===4 && dep ===s.length 达到四个并且元素用完; 【循环逻辑】: 正序，start为dep, 初始0，dep为i+1，【优化剪枝】:1. s.slice(dep, i+1)  长度>3 && >255, break; 2.长度大于1，第一位是0，break；3.temp.length > 4,return.
// 注意：放入的元素是s.slice(dep, i+1)
function restoreIpAddresses(s) {
  let res = [];
  let temp = [];
  let dep = 0;

  function backtracking(dep) {
    const len = temp.length;
    if (len > 4) return;
    if (len === 4 && dep === s.length) {
      res.push(temp.join('.'))
      return
    }
    for (let i = dep; i < s.length; i++) {

      const str = s.slice(dep, i + 1);

      if (str.length > 3 || +str > 255) break;
      if (str.length > 1 && str[0] === '0') break;

      temp.push(str);
      backtracking(i + 1);
      temp.pop();
    }
  }

  backtracking(dep)
  return res;
}
console.log(restoreIpAddresses("25525511135"))

// 8. 求子集
// 题解：不重复数组的，不重复子集
// 思路：【解空间】: 目标数组 【终止条件】: 所有可能 【循环逻辑】: 正序，start为dep, 初始0，dep为i+1，【优化剪枝】: 无
// 注意：终止没有任何限制条件，所有都终止
function findChild(arr) {
  let res = [];
  let temp = [];
  let dep = 0;

  function backtracking(temp, dep) {
    res.push(temp)
    for (let i = dep; i < arr.length; i++) {
      temp.push(arr[i])
      backtracking(temp.slice(), i + 1);
      temp.pop()
    }
  }
  backtracking(temp, dep);
  return res;
}
console.log(findChild([1, 2, 3]))

// 9. 求子集2
// 题解：有重复数组的，不重复子集
// 思路：【解空间】: 目标数组 【终止条件】: 所有可能 【循环逻辑】: 正序，start为dep, 初始0，dep为i+1，【优化剪枝】: 1.当i > dep && arr[i] - arr[i - 1] 判断相邻两个相等，则continue 同组合2 的不重复判定一样
// 注意：终止没有任何限制条件，所有都终止
function findChild2(arr) {
  nums.sort((a,b)=> a-b)
  let res = [];
  let temp = [];
  let dep = 0;

  function backtracking(temp, dep) {
    res.push(temp)
    for (let i = dep; i < arr.length; i++) {
      if (i > dep && arr[i] === arr[i - 1]) continue;
      temp.push(arr[i])
      backtracking(temp.slice(), i + 1);
      temp.pop()
    }
  }
  backtracking(temp, dep);
  return res;
}
console.log(findChild2([1, 2, 2]))

// 10.全排列 nums = [1,2,3]
// 题解：给一个数组，给出所有乱序的可能
// 思路：【解空间】: 目标数组 【终止条件】: arr.length === dep 【循环逻辑】: 正序， 循环起始是0【优化剪枝】: temp中已经存在过这个数字了，continue
// 注意：dep 不是i是dep+1，其实是temp.length; 
function getAll(arr) {
  let res = [];
  let temp = [];
  let dep = 0;
  function backtracking(temp, dep) {
    if (arr.length === dep) {
      res.push(temp.join(''))
      return
    }
    for (let i = 0; i < arr.length; i++) {
      if (temp.includes(arr[i])) continue
      temp.push(arr[i])
      backtracking(temp.slice(), i+1)
      temp.pop()
    }
  }
  backtracking(temp, dep);
  return res;
}
console.log(getAll([1, 2, 3]))

// 11. 全排列2 有重复元素
// 题解：给一个数组，给出所有乱序的可能，有重复数字
// 思路：【解空间】: 目标数组 【终止条件】: arr.length === dep 【循环逻辑】: 正序， 循环起始是0【优化剪枝】: 1.i > 0 && arr[i] === arr[i - 1] && !used[i - 1], continue 2. used[i], continue
// 注意：dep 不是i是dep+1，其实是temp.length; 多记录了一个used[i],use[i]也要回溯
function getAll2(arr) {
  arr.sort((a, b) => a - b)
  let res = [];
  let temp = [];
  let dep = 0;
  let used = new Array().fill(false)
  function backtracking(temp, dep) {
    if (arr.length === dep) {
      res.push(temp.join(''))
      return
    }
    for (let i = 0; i < arr.length; i++) {
      if (i > 0 && arr[i] === arr[i - 1] && !used[i - 1]) continue;
      if (used[i]) continue
      used[i] = true
      temp.push(arr[i])
      backtracking(temp, i + 1)
      used[i] = false
      temp.pop()
    }
  }
  backtracking(temp, dep);
  return res;
}
console.log(getAll2([1, 1, 2]))

// 12.n皇后 给一个n*n的棋盘
// 题解：给一个n*n的棋盘，每个皇后，同行同列，同斜线不会相交
// 思路：【解空间】: n棋盘 【终止条件】: n === dep 【循环逻辑】: 正序， 循环起始是0【优化剪枝】: 1.如果当前点的所在的列，所在的对角线都没有皇后，即可选择，否则，跳过
// 注意：正斜线：row+col 反斜线： row-col
function solveNQueens(n) {
  // 初始化棋盘
  const board = new Array(n);
  for (let i = 0; i < n; i++) {
    board[i] = new Array(n).fill('.')
  }

  const cols = new Set(); // 列集，记录出现过皇后的列
  const diag1 = new Set(); // 正对角线集合
  const diag2 = new Set(); // 反对角线集合
  const res = []
  const dep = 0;

  const backtracking = (row) => {
    if (row == n) {
      const stringsBoard = board.slice();
      for (let i = 0; i < n; i++) {
        stringsBoard[i] = stringsBoard[i].join('')
      }
      res.push(stringsBoard)
      return
    }
    for (let col = 0; col < n; col++) {
      // 如果当前点的所在的列，所在的对角线都没有皇后，即可选择，否则，跳过
      if (!cols.has(col) && !diag1.has(row + col) && !diag2.has(row - col)) {
        board[row][col] = 'Q';
        cols.add(col);
        diag1.add(row + col);
        diag2.add(row - col);
        backtracking(row + 1)
        board[row][col] = '.';
        cols.delete(col)
        diag1.delete(row + col);
        diag2.delete(row - col);
      }
    }
  }
  backtracking(dep)
  return res
}
console.log(solveNQueens(4))


// 13.单词搜索
// 在棋盘中搜索单词路径
var exist = function(board, word) {

  const m = board.length;
  const n = board[0].length;
  const used = Array.from(Array(m), () => Array(n).fill(false))

  // 判断当前点是否是目标路径上的点, i当前word字符索引
  const canFind = (row, col, i) => {
      if(i === word.length) return true; // i越界
      if(row < 0 || row >= m || col < 0 || col >= n){ // 点越界
          return false
      }
      if(used[row][col] || board[row][col] != word[i]){ // 当前结点被访问过
          return false
      }

      used[row][col] = true; // 记录当前几点被访问了
      // 能找到剩余字符路径
      const canFindRest = canFind(row+1, col, i+1) 
          || canFind(row-1,col, i+1) 
          || canFind(row, col+1, i+1) 
          || canFind(row, col-1, i+1)

      if(canFindRest) return true;

      used[row][col] = false; // 剩下字符找不到路径，撤销当前结点的使用状态
      return false
  }

  for(let i = 0; i< m; i++){
      for(let j =0; j< n; j++){
          if(board[i][j] === word[0] && canFind(i,j, 0)){ // 找到起始点，并且后续部分能被匹配
              return true 
          }
      }
  }

  return false

};


